package tree;

/**
 * 二叉树查找关键字
 * 必须有序
 *
 * @Author: ykl
 * @Description: Created by ykl on 2019/7/26.
 */
public class RecursionBinary {

//    循环实现二分查找
    private static int findByKey(int[] arr, int key) {
        int left = 0;
        int right = arr.length - 1;
        //中间数的下标
        int mid = (left + right) / 2;
        while (left <= right) {   //退出循环的条件  若一直没找到这个数，则会退出循环
            if (arr[mid] == key) { //数组中间的数正好是被查找的数直接返回
                return arr[mid];
            }
            if (arr[mid] < key) {
                left = mid + 1; //若小于被查找的数 则证明被查找的数只可能在数组右部分，则将右部分的数组重新进行一次二分查找
            } else {
                right = mid - 1;//同理
            }
            mid = (left + right) / 2;
        }
        return -1;
    }

//    递归实现二分查找
    private static int rank(int[] arr, int key , int left, int right){
        if (left >= right){
            return -1;
        }
        int mid = (left + right) / 2;
        if (arr[mid] == key){
            return arr[mid];
        }
        if (arr[mid] < key){
            return rank(arr, key, mid + 1, right);
        }
        return rank(arr, key, left, mid - 1);
    }

    public static void main(String[] args) {
        int[] arr = new int[5];
        for (int i = 0; i < 5; i++) {
            arr[i] = i * 10;
        }
        int key = 30;
//        int value = findByKey(arr, key);
        int value = rank(arr, key, 0, arr.length - 1);
        if (value != -1) {
            System.out.println("find key.value=" + value);
        } else {
            System.out.println("not find key:" + key);
        }
    }
}
